/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import com.leetCode.structure.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/14
 */
public class _16_111_MinimumDepthOfBinaryTree {

    public static int minDepth1(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node;
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                node = queue.poll();
                if (node.left == null && node.right == null) return level;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return level;
    }

    public static int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0)
                ? left + right + 1 : Math.min(left, right) + 1;
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(3);
        TreeNode t2 = new TreeNode(9);
        TreeNode t3 = new TreeNode(20);
        t1.left = t2;
        t1.right = t3;
        TreeNode t4 = new TreeNode(15);
        TreeNode t5 = new TreeNode(7);
        t3.left = t4;
        t3.right = t5;
        System.out.println(minDepth(t1));
    }
}
